367. 有效的完全平方数

题目链接

分析

什么是完全平方数？如果一个正整数 a 是某一个整数 b 的平方，那麼這个正整数 a 叫做完全平方数。0 也可称为完全平方数。
有两点需要注意

• 首先排除 0
• 在判断平方相等的时候，要同时判断除数和余数，middle == num/middle 而且 num % middle == 0，middle 才是其平方根，如果余数不为 0，说明还是大了。
  这个题跟 69. x 的平方根 非常像，而且比 69 题简单，因为 69 题求的是平方根的整数部分，所以 mid*mid <= target 的时候 mid 就可能是我们的平方根，但是还需要等待跳出循环，我们才能确定最终的值，但是这个题目不存在这问题，这个题就是要找 mid*mid == target 的时候的值，因此，此题中，只需要 start，end，mid 这三个变量即可。不需要像 34. 在排序数组中查找元素的第一个和最后一个位置 一样用一个额外的对象来保存结果。

解题

public boolean isPerfectSquare(int num) {
    if(num ==0){
        return true;
    }
    int start=1,end=num;
    while(start<=end){
        int mid = start+(end-start)/2;
        if(mid == num/mid){
            // 光这个还不够，还得检查余数，才能保证是完全平方数
            if(num%mid == 0){
                return true;
            }else{
                // 如果余数不为0，那么还是大了
                end = mid-1;
            }
        }else if(mid > num/mid){
            end = mid-1;
        }else{
            start = mid+1;
        }
    }
    return false;
}

相关题

69. x 的平方根